package org.alg.sort;

public class QuickSort extends SortTemplate{
	private static int partition(Comparable[] a,int lo,int hi){
		int i=lo;
		int j=hi+1;
		Comparable v=a[lo];
		while(true){
			while(less(a[++i],v))if(i==hi)break;
			while(less(v,a[--j]))if(j==lo)break;
			
			if(i>=j)break;
			exch(a,i,j);
		}
		
		exch(a,lo,j);
		return j;
	}
	
	public static void sort(Comparable[] a,int lo,int hi){
		if(hi<=lo)return;
		int j=partition(a,lo,hi);
		sort(a,lo,j-1);
		sort(a,j+1,hi);
	}
	
	public static void main(String[] args){
		Integer[] a=new Integer[]{10,20,4,60,5,4,25,58,6,2,58,2,6};
		sort(a,0,a.length-1);
		show(a);
	}
}
